0% completed
Problem Statement
Given a signed 32-bit integer x, return the reverse of x. If the reversed value of x goes beyond the signed 32-bit integer range [-231, 231 - 1], then return 0.
A reverse of x should not contain leading zeros.
Examples
-
Example 1:
- Input: x =
123 - Expected Output:
321 - Justification: Reversing the digits of 123 results in 321, which is within the 32-bit signed integer range.
- Input: x =
-
Example 2:
- Input: x =
-456432 - Expected Output:
-234654 - Justification: Reversing the digits of -456432 results in -234654, maintaining the negative sign and staying within the 32-bit signed integer range.
- Input: x =
-
Example 3:
- Input: x =
1200 - Expected Output:
21 - Justification: Reversing the digits of 1200 results in 0021, but leading zeros are dropped, resulting in 21.
- Input: x =
Solution
To solve this problem, we'll take a mathematical approach to reverse the digits of the given integer. This approach is effective because it directly manipulates the numerical value, allowing us to easily handle both positive and negative numbers and check for overflow conditions. The essence of the solution is to iteratively extract the last digit of the current number, append it to the reversed number, and then remove that digit from the original number by division. This process repeats until all digits have been processed.
The key to handling overflow is to check if the new reversed number, when multiplied back by 10 (to add a new digit), would exceed the 32-bit integer limit. By performing this check before actually appending the next digit, we can ensure that our function never produces an overflowed result. This method is not only straightforward but also efficient, as it requires no additional data structures and operates in linear time complexity relative to the number of digits in the input.
Step-by-step Algorithm
- Initialize a variable
reversedto store the reversed number, starting at 0. - While the input number
xis not 0:- Extract the last digit of
xby takingx % 10. - Check for overflow/underflow before appending the digit to
reversed. If appending would cause overflow or underflow, return 0. - Append the digit to
reversedby multiplyingreversedby 10 and adding the extracted digit. - Remove the last digit from
xby dividing it by 10.
- Extract the last digit of
- After the loop, if
reversedis within the 32-bit signed integer range, returnreversed. Otherwise, return 0.
Algorithm Walkthrough
Let's consider the Input: -456432
-
Initialize Variables:
- Set
reversedto 0. This variable will hold our reversed number as we build it. - The input
xis (-456432).
- Set
-
Iteration 1:
- Extract the last digit: (x % 10 = -2).
- Append
-2toreversed: (reversed = reversed * 10 - 2 = -2). - Update
xby removing the last digit: (x = x / 10 = -45643).
-
Iteration 2:
- Extract the last digit: (x % 10 = -3).
- Append
-3toreversed: (reversed = -2 * 10 - 3 = -23). - Update
x: (x = x / 10 = -4564).
-
Iteration 3:
- Extract the last digit: (x % 10 = -4).
- Append
-4toreversed: (reversed = -23 * 10 - 4 = -234). - Update
x: (x = x / 10 = -456).
-
Iteration 4:
- Extract the last digit: (x % 10 = -6).
- Append
-6toreversed: (reversed = -234 * 10 - 6 = -2346). - Update
x: (x = x / 10 = -45).
-
Iteration 5:
- Extract the last digit: (x % 10 = -5).
- Append
-5toreversed: (reversed = -2346 * 10 - 5 = -23465). - Update
x: (x = x / 10 = -4).
-
Iteration 6:
- Extract the last digit: (x % 10 = -4).
- Append
-4toreversed: (reversed = -23465 * 10 - 4 = -234654). - Update
x: (x = x / 10 = 0).
-
Final Check and Return:
- At this point,
xis 0, so we exit the loop. - Return
reversed, which is (-234654).
- At this point,
Code
Complexity Analysis
Time Complexity
The time complexity of the reverse integer algorithm is
Space Complexity
The space complexity of the algorithm is
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity